#include "main/utils.h"
using namespace std;

vector<int> asteroidCollision(const vector<int>& vec) {
  stack<int> help_stack;
  for (int i = 0; i < vec.size(); ++i) {
    if (vec[i] < 0) {
      while (!help_stack.empty() && help_stack.top() > 0 && help_stack.top() < -1 * vec[i]) {
        help_stack.pop();
      }

      if (!help_stack.empty() && help_stack.top() == -1 * vec[i]) {
        help_stack.pop();
      } else if (!help_stack.empty() && help_stack.top() > -1 * vec[i]) {
      } else {
        help_stack.push(vec[i]);
      }
    } else {
      help_stack.push(vec[i]);
    }
  }

  vector<int> ret;
  ret.resize(help_stack.size());
  for (int i = ret.size() - 1; i >= 0; --i) {
    ret[i] = help_stack.top();
    help_stack.pop();
  }
  return ret;
}

int main() {
  vector<int> vec = {4, 5, -6, 4, 8, -5};
  auto ret = asteroidCollision(vec);
  printVec("asteroidCollision", ret);

  return 0;
}
